package 中等.双指针;

import util.ListNode;

/**
 * 给定一个已排序的链表的头 head ， 删除原始链表中所有重复数字的节点，
 * 只留下不同的数字 。返回 已排序的链表 。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/remove-duplicates-from-sorted-list-ii/
 */
public class 删除排序链表中的重复元素II_82 {

    public static void main(String[] args) {

        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(2);
        ListNode node4 = new ListNode(3);
        ListNode node5 = new ListNode(3);
        ListNode node6 = new ListNode(4);
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
        node5.next = node6;
        deleteDuplicates(node1);

    }

    /**
     * 双指针
     * 可以用一个虚拟头结点来删除原链表中的头结点
     * 如果当前指针的后面存在 2 个以上的重复元素，那么当前节点的下一个节点
     * 为删除重复元素的第一个节点
     * 否则后面一个节点不需要删除，当前节点遍历到下一个节点
     */
    public static ListNode deleteDuplicates(ListNode head) {
        ListNode virtualHead = new ListNode(-101);
        virtualHead.next = head;

        ListNode curNode = virtualHead;

        while (curNode != null) {
            if (curNode.next != null && curNode.next.next != null &&
                    curNode.next.val == curNode.next.next.val) {

                ListNode tempNode = curNode.next;
                while (tempNode.next != null && tempNode.val == tempNode.next.val) {
                    tempNode = tempNode.next;
                }
                curNode.next = tempNode.next;
            } else {
                curNode = curNode.next;
            }
        }

        return virtualHead.next;
    }

}
